\documentclass[twocolumn,a4paper]{article}
\usepackage{geometry}
\usepackage{xeCJK}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}

% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
% draw packages
\usepackage{tikz}
\usepackage{forest}


\def\b{\boldsymbol{}}
\def\v{\vert}
\def\V{\Vert}

\begin{document}
	
	\pagestyle{fancy}
	\fancyhead{}
	\lhead{Haolong Li(3180105433)}
	\chead{NPDE Homework \#01}
	\rhead{\today}
	
\section*{Introduction}
Exercise 7.9, 7.14, 7.15, 7,17, 7.21, 7.38, 7.57, 7.110, 7.112, 7.113, 7.118, 7.119
are I, II, III, IV, V, VI, VII, VIII, IX, X, XI correspondingly.



\section*{I. Verify that (7.7) is indeed a norm in the sense of Definition B.84.}

\begin{proof}
(NRM-1) real positivity: 
\[ \V T \V = \inf \{ M: \forall \b{x} \in \mathbb{F}^{n}, \v T \b{x} \v \leq M\v \b{x} \v \} \]

and $\v \b{x} \v \geq 0 ,\quad \v T \b{x} \v \geq 0$, since $M \geq 0, \quad \V T \V \geq 0$

(NRM-2) point separation:
\[
\V T \V = 0 \Rightarrow \v T \b{x} \v \leq 0 \Rightarrow \v T \b{x} \v = 0
\]

(NRM-3) absolute homogeneity:
\[
\forall a \in \mathbb{F}, \forall T \in \mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m}), \]
\[
 \V aT \V =\inf \{M:\forall  \b{x} \in \mathbb{F}^{n}, \v aT \b{x} \v \leq M \v \b{x} \v \}
\]
where $\v aT \b{x} \v =\v a \v \v T \b{x} \v$, since
\[
\V aT \V = \v a \v \V T \V
\]

(NRM-4) triangle inequality: 
\[
\forall T,S \in \mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m}), 
\]
\[
\V T+S \V = \inf \{M_{1}:\forall  \b{x} \in \mathbb{F}^{n}, \v (T+S) \b{x} \v \leq M_{1} \v \b{x} \v \}
\]
where 
\[
\v (T+S)\b{x} \v \leq \v T\b{x} \v + \v S\b{x} \v 
\]
$\Rightarrow$
\[
 \V T+S \V \leq \V T \V + \V S \V
\]
\end{proof}

\section*{II. Verify that the space $\mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m})$ becomes a metric space if we define the metric as $d(T,S)=\V T-S \V$.}
\begin{proof}
(1) positive definiteness: This follows the real positivity and the point separation directly showed above.

(2) symmetry： 
\begin{align*}
d(T,S) &= \V T-S \V \\
&= \inf \{ M:\forall \b{x} \in \mathbb{F}^{n}, \v (T-S)\b{x} \v \leq M \v \b{x} \v \} \\
&=\inf \{ M:\forall \b{x} \in \mathbb{F}^{n}, \v (S-T)\b{x} \v \leq M \v \b{x} \v \} \\
&= \V S-T \V \\
&= d(S,T) 
\end{align*}

(3) the triangle inequality: This follows the  
triangle inequality of the operator norm $\V  \cdot \V$ directly.

\end{proof}

\section*{III. For $T \in \mathcal{L}(\mathbb{C}^{n},\mathbb{C}^{m})$, suppose $T\b{e}_{j} \in \mathbb{R}^{m}$ for each standard basis vectors, i.e., $j=1,...,n.$Prove that $\V T \V$ is consistently defined in the sense that \[ \V T \V=\sup\limits_{\b{x} \in \mathbb{R}^{n};\v \b{x} \v \leq 1}\v T\b{x} \v = \sup\limits_{\b{z} \in \mathbb{C}^{n};\v \b{z} \v \leq 1}\v T\b{z} \v. \]}

\begin{proof}
set $\b{z}= \b{x}+ i\b{y}$, where $x^{2}+y^{2}=1$, then
\begin{align*}
\v T \b{z} \v &= \v T (\b{x}+i\b{y}) \v =\sqrt{\v (T \b{x}+T \b{y}) \v^{2}} \\
&\leq \sqrt{\V T \V ^{2}(\b{x}^{2}+\b{y}^{2})}=\V T \V = \sup_{\b{x} \in \mathbb{R}^{n};\v \b{x} \v \leq 1}\v T \b{x} \v
\end{align*}


\end{proof}

\section*{IV. Verify that (7.10) is indeed a norm in the sense of Definition B.84.}
\begin{proof}
(NRM-1) real positivity: 
\[
\forall T \in \mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m}),
\]
\[
\v T \v = (\sum_{j=1}^{n}\v T\b{e}_{j} \v ^{2})^{\frac{1}{2}} \geq 0
\]

(NRM-2) point separation:


Thus
\[
\v T \b{e}_{j} \v ^{2} \geq 0, 
\]
\[
\v T \v = (\sum_{j=1}^{n}\v T\b{e}_{j} \v ^{2})^{\frac{1}{2}} = 0
\]
$\Rightarrow$
\[
\v T \b{e}_{j} \v  = 0
\]

(NRM-3) absolute homogeneity:
\[
\forall a \in \mathbb{F}, \forall T \in \mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m}),
\]
\begin{align*}
\v aT \v &= (\sum_{j=1}^{n}\v aT\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
 &= \v a \v (\sum_{j=1}^{n}\v T\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
 &= \v a \v \v T \v
\end{align*}

(NRM-4) triangle inequality:
\[
\forall T,S \in \mathbb{F}, \forall T \in \mathcal{L}(\mathbb{F}^{n},\mathbb{F}^{m}),
\]
\begin{align*}
\v T+S \v &= (\sum_{j=1}^{n}\v (T+S)\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
&= (\sum_{j=1}^{n}\v T\b{e}_{j}+S\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
&\leq  (\sum_{j=1}^{n}\v T\b{e}_{j} \v ^{2})^{\frac{1}{2}}+(\sum_{j=1}^{n}\v S\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
&= \v T \v + \v S \v
\end{align*}

\end{proof}

\section*{V. Prove Corollary 7.20.}
\begin{proof}

\begin{align*}
\v T \v \v S \v &= (\sum_{j=1}^{n}\v T \b{e}_{j} \v ^{2})^{\frac{1}{2}}(\sum_{j=1}^{n}\v S \b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
&\geq (\sum_{j=1}^{n}(\v T\b{e}_{j} \v \v S\b{e}_{j}\v)^{\frac{1}{2}} \\
&= (\sum_{j=1}^{n}\v \v S \b{e}_{j}\v T \b{e}_{j} \v)^{\frac{1}{2}} \\
&=(\sum_{j=1}^{n}\v T(S \b{e}_{j}) \v)^{\frac{1}{2}} \\
&= (\sum_{j=1}^{n}\v (TS)\b{e}_{j} \v ^{2})^{\frac{1}{2}} \\
&= \v TS \v
\end{align*}

The second inequation follows Cauchy Inequation.

\end{proof}

\section*{VI. Prove Theorem 7.37}
\begin{proof}
We know there exists matrix A ,s.t. $AXA^{-1}$ is upper triangular matrix, and all elements on its diagonal is eigen of A, and $tr(AXA^{-1})=tr(X)$

Then we have:
\begin{align*}
\det(e^{X})&=\det(Ae^{X}A^{-1})=det(e^{AXA^{-1}})\\
&=e^{tr(AXA^{-1})}=e^{tr(X)}
\end{align*}
\end{proof}

\section*{VII. Show that \[ p_{M}(z) = z^{s}+\sum_{j=0}^{s-1}\alpha_{j}z^{j}. \] is the characteristic polynomial of \[ M= \begin{bmatrix}
0 & 1 & & & \\ & 0 & 1 & & \\ & & \ddots & \ddots & \\ & & & 0 & 1 \\ -\alpha_{0} & -\alpha_{1} & \cdots & -\alpha_{s-2} & -\alpha_{s-1}
\end{bmatrix}  \]
$\in \mathbb{C}^{s \times s}.$}
\begin{proof}
Following the Factorization of a polynomial over $\mathbb{C}$:(7.29), 
\begin{align}
p_{M}(z)&=det(zI-M) \notag \\
&=c(z-\lambda_{1})(z-\lambda_{2}) \cdots (z-\lambda_{s}) 
\end{align}
where $c,\lambda_{1},\cdots,\lambda_{s} \in \mathbb{C}$

In another hand, follow the (B.40)
\[
det(zI-M)=\sum_{\sigma \in S_{s}}sgn(\sigma)\prod_{i=1}^{s}a_{\sigma(i),i}
\]

within the coefficient of $z^{s}$ is 1 obviously, so the $c$ in (1) is 1.

And still, it's trivial that $\lambda_{1},\cdots,\lambda_{s}$ are the eigenvalues of M by using definition.

So 
\begin{align}
p_{M}(z)=&z^{s}-C_{s}^{s-1}z^{s}\sum_{i=1}^{s}\lambda_{i} \notag \\ &+C_{s}^{s-2}z^{s-1}\sum_{i,j \in {1,\cdots,s},i \neq j}\lambda_{i}\lambda_{j}-\cdots+(-1)^{s}\prod_{i=1}^{s}\lambda_{i}
\end{align}
All we need to proof is the coefficients in (1) and (2) are equal to each other， and this follows directly from Vieta theorem.

\end{proof}

\section*{VIII. Compute the first five coefficients $C_{j}$'s of the trapezoidal rule and the midpoint rule from Examples 7.96 and 7.98.}
Solution:

The trapezoidal rule:
\begin{align*}
&C_{0}=\sum_{j=0}^{s}\alpha_{j}=0 \\
&C_{1}=0 \\
&C_{2}=0 \\
&C_{3}=-\frac{1}{12} \\
&C_{4}=-\frac{1}{12}
\end{align*}
The midpoint rule:
\begin{align*}
&C_{0}=0 \\
&C_{1}=0 \\
&C_{2}=0 \\
&C_{3}=\frac{1}{3} \\
&C_{4}=\frac{1}{3}
\end{align*}
\hfill \qedsymbol

\section*{IX. Express comditions of $\mathcal{L}=O(k^{3})$ using characteristic polinomials}
Solution:
$\mathcal{L} = O(k^{3})$ actually means 2-th order accuracy, which means 
\[
\sum_{j=0}^{s}\alpha_{j}=0, \quad \sum_{j=0}^{s}j \alpha_{j} = \sum_{j=0}^{s} \beta_{j}, \quad \frac{1}{2}\sum_{j=0}^{s}j^{2}\alpha_{j}=\sum_{j=0}^{s}j\beta_{j}.
\]
which is equivalent to
\[
\rho(1)=0, \quad \rho'(1)= \sigma (1), \quad  \frac{1}{2}(\rho''(1)+\rho'(1))=\sigma'(1)
\]

\hfill \qedsymbol

\section*{X. Derive coefficients of LMMs shown below by the method of undetermined coefficients and a programming language with symbolic computation such as Matlab.}
Solution: 

Adams-Bashforth formulas:

(1) $C_{0}=0,C_{1}=0,C_{2}=0.50000,C_{3}=0.16667$

(2) $C_{1}=0,C_{2}=0,C_{3}=0.41667,C_{4}=0.37500$

(3) $C_{2}=0,C_{3}=0,C_{4}=0.37500,C_{5}=0.53611$

(4) $C_{3}=0,C_{4}=0,C_{5}=0.19444,C_{6}=0.39583$

Adams-Moulton formulas:

(1) $C_{1}=0,C_{2}=0,C_{3}=-0.083333,C_{4}=-0.041667$

(2) $C_{2}=0,C_{3}=0,C_{4}=-0.041667,C_{5}=-0.047222$

(3) $C_{3}=0,C_{4}=0,C_{5}=-0.037008,C_{6}=-0.053542$

(4) $C_{4}=0,C_{5}=0,C_{6}=-0.018750,C_{7}=-0.042394$

Backwards differentiation formulas:

(1) $C_{0}=0,C_{1}=0,C_{2}=2.2204e-16,C_{3}=-0.083333$

(2) $C_{1}=0,C_{2}=0,C_{3}=1.1111,C_{4}=0.61111$

(3) $C_{2}=0,C_{3}=0,C_{4}=2.3182,C_{5}=1.5955$

(4) $C_{3}=0,C_{4}=0,C_{5}=5.1200,C_{6}=5.0240$

More details are contained in the package submitted, where octave code is included in E\_ 7 \_133.m and output pdf is E \_ 7 \_113.pdf.

\hfill \qedsymbol

\section*{XI. For the third-order BDF in Definition 7.99 and Exercise 7.113, derive its characteristic polynomials and apply Theorem 7.116 to verify that the order of accuracy is indeed 3.}
\begin{proof}

\[
\rho(z)=-\frac{1}{2}+\frac{9}{11}z-\frac{18}{11}z^{2}+z^{3},\sigma(z)-\frac{27}{22}+\frac{18}{11}z-\frac{9}{22}z^{2}+\frac{6}{11}z^{3}
\]
\[
\frac{\rho(z)}{\sigma(z)}=(z-1)(1-\frac{z-1}{2}+\frac{(z-1)^{2}}{3}- \cdots)
\]
which confirms the order of accuracy is indeed 3.

\end{proof}


\section*{XII. Prove that an s-step LMM has order of accuracy p if and only if, when applied to an ODE $u_{t}=q(t)$, it gives exact results whenever $q$ is a polynomial of degree $< p$, but not whenever $q$ is a polymial of  degree $p$.Assume arbitrary continuous initial data $u_{0}$ and exact numercial initial data $v^{0},\cdots,v^{s-1}$}
\begin{proof}
Following Lemma 7.105, if $q$ is apolynomial of degree $\leq p$, then when using LMM, terms expect the first $p+1$ are $0$ because $q$'s p-th and higer derivatives are $0$, so it gives exact results, and not whenever $q$ is a polymial of degree $p$.


If it gives exact results whenever $q$ is a polynomial of degree $< p$, but not whenever $q$ is a polymial of  degree $p$, it's trivial following Lemma 7.105 that the first $p+1$ terms are 0, so the LMM has order of accuracy $p$.

\end{proof}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
